package com.itheima.algorithm.heap;

/**
 * @author: TylerZhong
 * @description:
 * 解题思路
 *
 *  1. 向小顶堆放入前 K 个元素
 *  2. 剩余元素
 *      若 <= 堆顶元素，则略过
 *      若 > 堆顶元素，则替换堆顶元素
 *  3. 这样小顶堆始终保留的是到目前为止，前 K 大的元素
 *  4. 循环结束，堆顶元素即为第 K 大元素
 */
public class E02Leetcode215 {

    public int findKthLargest(int[] numbers, int k) {
        MinHeap minHeap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            minHeap.offer(numbers[i]);
        }
        for (int i = k; i < numbers.length; i++) {
            if (minHeap.peek() < numbers[i]) {
                minHeap.replace(numbers[i]);
            }
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        // 应为5
        System.out.println(new E02Leetcode215().findKthLargest(new int[]{3,2,1,5,6,5}, 2));
        // 应为4
        System.out.println(new E02Leetcode215().findKthLargest(new int[]{3,2,1,2,4,5,5,6}, 4));
    }

}
